#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 041. 缺失的第一个正数.py
@time: 2022/1/20 0:45
@desc: https://leetcode-cn.com/problems/first-missing-positive/
> 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

1. 解法一，老实人：Ot(n), Os(1)
2. 解法二， 原地哈希：时间复杂度：Ot(N), Os(1)
'''

# 老实人解法
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return
        nums.sort()
        start = 1
        for num in nums:
            if num>start:
                return start
            if num==start:
                start += 1
        return start

# 原地哈希（妖艳贱货）
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= len(nums) and not nums[i]==nums[nums[i]-1]:
                # 交换位置, 这里如果写反了出错，很诡异
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

        for i in range(n):
            if not i + 1 == nums[i]: return i + 1

        return n + 1

if __name__ == '__main__':
    nums = [3,4,-1,1]
    res = Solution().firstMissingPositive(nums)
    print(res)